/*
 * cover_tree_impl.h
 *
 *  Created on: Jun 1, 2011
 *      Author: tqlong
 */

#ifndef COVER_TREE_IMPL_H_
#define COVER_TREE_IMPL_H_
#include <stack>

template<typename D>
  CoverTree<D>::CoverTree(dataset_type& data) :
    data_(data), idx_(*new vint_type(data.n())), parent_(NULL), start_(0),
        end_(data.n())
  {
    for (int i = 0; i < n(); i++)
      idx_[i] = i;
  }

template<typename D>
  CoverTree<D>::CoverTree(CoverTree* parent, int start, int end, double level,
      bool isSelf) :
    data_(parent->data_), idx_(parent->idx_), parent_(parent), start_(
        parent_->start_ + start), end_(parent_->start_ + end), level_(level),
        isSelfChild_(isSelf)
  {
  }

template<typename D>
  CoverTree<D>::~CoverTree()
  {
    for (int c = 0; c < n_child(); c++)
      delete child(c);
    if (!parent_) delete &idx_;
  }

template<typename D>
  void
  CoverTree<D>::buildTree()
  {
    static double min_level = 1e10;
    if (n() <= 1) return;
    if (!parent_) // check if it is root
      {
        isSelfChild_ = true;
        int center = rand() % n();
        swap(0, center);
        double max_distance = 0;
        for (int i = 1; i < n(); i++)
          {
            double dist = distance(0, i);
            if (dist > max_distance) max_distance = dist;
          }
        level_ = floor(log2(max_distance)) + 1;
        std::cout << "center=" << origIdx(0) << " max_dist=" << max_distance
            << " level=" << level_ << std::endl;
      }

    if (level_ < min_level) min_level = level_;

    split();

    // a self-child and all points can be covered by half radius, try half radius again
    if (n_child() == 0) buildTree();
    // otherwise
    for (int c = 0; c < n_child(); c++)
      child(c)->buildTree();

    if (!parent_) std::cout << "min_level=" << min_level << std::endl;
  }

template<typename D>
  void
  CoverTree<D>::split()
  {
    //    std::cout << "level=" << level_ << std::endl;
    // try to cover with half-radius 2^(level-1)
    int pos = 1;
    for (int i = 1; i < n(); i++)
      {
        double dist = distance(0, i);
        if (log2(dist) <= level_ - 1) swap(pos++, i);
      }
    //    std::cout << "pos=" << pos << std::endl;
    if (pos >= n()) // all points covered
      {
        if (!isSelfChild_) // only create new self-child if this is not a self-child
          {
            addChild(new CoverTree(this, 0, n(), level_ - 1, true));
          }
        else // otherwise, half the radius
          {
            level_--;
          }
      }
    else // some points are not covered
      {
        addChild(new CoverTree(this, 0, pos, level_ - 1, false));
        while (pos < n())
          {
            int center = rand() % (n() - pos) + pos;
            swap(pos, center);
            center = pos++;
            for (int i = center + 1; i < n(); i++)
              {
                double dist = distance(center, i);
                if (log2(dist) <= level_ - 1) swap(pos++, i);
              }
            //            std::cout << "pos=" << pos << std::endl;
            addChild(new CoverTree(this, center, pos, level_ - 1, false));
          }
      }
  }

template<typename D>
  void
  CoverTree<D>::save(std::ostream& f)
  {
    if (!parent_)
      {
        f << n() << std::endl;
        for (int i = 0; i < n(); i++)
          f << idx_[i] << " ";
        f << std::endl;
      }
    f << start_ << " " << end_ << " " << level_ << " " << isSelfChild_ << std::endl;
    for (int c = 0; c < n_child(); c++)
      child(c)->save(f);
    if (!parent_)  // mark the end of file
      f << "-1 -1 -1 1" << std::endl;
  }

template<typename D>
  void
  CoverTree<D>::save(const std::string& fName)
  {
    std::ofstream f(fName.c_str());
    save(f);
    f.close();
  }

template<typename D>
  void
  CoverTree<D>::load(std::istream& f)
  {
    if (parent_) return; // use on root only;

    int start, end;
    double level;
    bool isSelf;
    std::stack<CoverTree*> s;

    int k;
    f >> k;
    assert(k == n()); // can be removed if tree data is a subset of original data
    for (int i = 0; i < k; i++)
      f >> idx_[i];
    f >> start_ >> end_ >> level_ >> isSelfChild_;
    s.push(this);

    f >> start >> end >> level >> isSelf; // read children (start, end)
    while (!s.empty())
      {
        if (start == -1 || end == -1) break;   // end of file
        CoverTree *node = s.top();
        if (node->start_ <= start && node->end_ >= end)
          {
            CoverTree *c = new CoverTree(node, start - node->start_, end - node->start_, level, isSelf);
            node->addChild(c);
            s.push(c);
            f >> start >> end >> level >> isSelf;  // read children (start, end)
          }
        else
          s.pop();   // this node is done loading data
      }
  }

template<typename D>
  void
  CoverTree<D>::load(const std::string& fName)
  {
    std::ifstream f(fName.c_str());
    load(f);
    f.close();
  }

template<typename D>
  void
  CoverTree<D>::dump(int level)
  {
    for (int i = 0; i < level; i++)
      std::cerr << "  ";
    std::cerr << "(";
    for (int i = 0; i < n(); i++)
      std::cerr << origIdx(i) << ", ";
    std::cerr << ")" << std::endl;
    for (int c = 0; c < n_child(); c++)
      child(c)->dump(level + 1);
  }

#endif /* COVER_TREE_IMPL_H_ */
